package com.example.lcode.greedy;

import java.util.Arrays;

/**
 * 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
 *
 * 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
 *
 * 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
 *
 * 输入：[[1,2], [2,3], [3,4]]
 * 输出：2
 * 解释：最长的数对链是 [1,2] -> [3,4]
 *
 */
public class Question646 {

    public int findLongestChain(int[][] pairs) {
        if (pairs.length <= 1) {
            return pairs.length;
        }
        Arrays.sort(pairs, (o1, o2) -> {
            if (o1[0] - o2[0] > 0) {
                return 1;
            }else if (o1 == o2) {
                return 0;
            }
            return -1;
        });
        int right = pairs[0][1];
        int res = 1;
        for (int i = 1; i < pairs.length; i++) {
            if (right >= pairs[i][0]) {
                if (right < pairs[i][1]) {
                    continue;
                }
            } else {
                res ++;
            }
            right = pairs[i][1];
        }
        return res;
    }

    public static void main(String[] args) {
        int [][]arr = {{1,2},{2,3},{3,4}};
        Question646 question646 = new Question646();
        int longestChain = question646.findLongestChain(arr);
        System.out.println(longestChain);
    }

}
